#include <limits>
#include "outline/outline.h"
#include "imglib/bitmap.h"
#include "imglib/boundmap.h"

namespace outline {

static void trace_contour(img::bitmap const & b, outline_us & o, img::boundmap & bounds, bool force_close)
{
	point_us p = o.back();
	for (;;) {
		bool left = p.x == 0;
		bool right = p.x >= b.width(); 
		bool x_bound = left || right;
		bool top = p.y == 0;
		bool bottom = p.y >= b.height(); 
		bool y_bound = top || bottom;
		if (!force_close && (x_bound || y_bound))
			break;
		///look for possible continuation
		if (!left && 
			!bounds.horiz_cut(p.y, p.x-1) &&
			(top && b(p.x-1, p.y) || bottom && b(p.x-1, p.y-1) || !y_bound && b(p.x-1, p.y-1) != b(p.x-1, p.y))) 
		{
			bounds.horiz_cut(p.y, p.x-1) = true;
			--p.x;
		}
		else 
		if (!right && 
			!bounds.horiz_cut(p.y, p.x) &&
			(top && b(p.x, p.y) || bottom && b(p.x, p.y-1) || !y_bound && b(p.x, p.y-1) != b(p.x, p.y))) 
		{
			bounds.horiz_cut(p.y, p.x) = true;
			++p.x;
		}
		else 
		if (!top && 
			!bounds.vert_cut(p.x, p.y-1) &&
			(left && b(p.x, p.y-1) || right && b(p.x-1, p.y-1) || !x_bound && b(p.x-1, p.y-1) != b(p.x, p.y-1))) 
		{
			bounds.vert_cut(p.x, p.y-1) = true;
			--p.y;
		}
		else 
		if (!bottom && 
			!bounds.vert_cut(p.x, p.y) &&
			(left && b(p.x, p.y) || right && b(p.x-1, p.y) || !x_bound && b(p.x-1, p.y) != b(p.x, p.y))) 
		{
			bounds.vert_cut(p.x, p.y) = true;
			++p.y;
		}
		else
			break;
		o.push_back(p);
	}
}

void trace(img::bitmap const & b, outlines_us & os, bool close_all)
{
	assert(std::numeric_limits<unsigned short>::max() >= b.width());
	assert(std::numeric_limits<unsigned short>::max() >= b.height());
	unsigned short w = b.width(), h = b.height();

	//traced cuts will be fixed here
	img::boundmap bounds(b.dim());
	bounds.fill(false);

	//first of all inspect bitmap's frame border to find all open contours
	for (unsigned short x = 1; x < w; ++x) {
		if (b(x, 0) && !b(x-1, 0) && !bounds.vert_cut(x, 0)) {
			bounds.vert_cut(x, 0) = true;
			os.push_back(outline_us());
			outline_us & o = os.back();
			o.push_back(point_us(x, 0));
			o.push_back(point_us(x, 1));
			trace_contour(b, o, bounds, close_all);
			assert(close_all == closed(o));
		}
		if (b(x-1, h-1) && !b(x, h-1) && !bounds.vert_cut(x, h-1)) {
			bounds.vert_cut(x, h-1) = true;
			os.push_back(outline_us());
			outline_us & o = os.back();
			o.push_back(point_us(x, h));
			o.push_back(point_us(x, h-1));
			trace_contour(b, o, bounds, close_all);
			assert(close_all == closed(o));
		}
	}
	for (unsigned short y = 1; y < h; ++y) {
		if (b(0, y-1) && !b(0, y) && !bounds.horiz_cut(y, 0)) {
			bounds.horiz_cut(y, 0) = true;
			os.push_back(outline_us());
			outline_us & o = os.back();
			o.push_back(point_us(0, y));
			o.push_back(point_us(1, y));
			trace_contour(b, o, bounds, close_all);
			assert(close_all == closed(o));
		}
		if (b(w-1, y) && !b(w-1, y-1) && !bounds.horiz_cut(y, w-1)) {
			bounds.horiz_cut(y, w-1) = true;
			os.push_back(outline_us());
			outline_us & o = os.back();
			o.push_back(point_us(w, y));
			o.push_back(point_us(w-1, y));
			trace_contour(b, o, bounds, close_all);
			assert(close_all == closed(o));
		}
	}

	//second: find closed contours inside the bitmap (it's enough to look for one type of cut)
	img::bitmap::const_iterator i;
	for (i = b.begin(); i != b.end(); ++i) {
		if (i.x() > 0 && *i && !i.rel(-1,0) && !bounds.vert_cut(i.x(), i.y())) {
			bounds.vert_cut(i.x(), i.y()) = true;
			os.push_back(outline_us());
			outline_us & o = os.back();
			o.push_back(point_us(i.x(), i.y()));
			o.push_back(point_us(i.x(), i.y()+1));
			trace_contour(b, o, bounds, close_all);
			assert(closed(o));
		}
	}
}

} //namespace outline
